class Solution {
    vector<vector<int>> ret;
    vector<int> path;
    bool chick[100];
    int sz;
    int target;

public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int _target) {
        sort(candidates.begin(), candidates.end());
        target = _target;
        sz = candidates.size();
        fill(chick, chick + sz, false);
        dfs(candidates, 0, 0);  // 第二个参数是 start，表示从哪个索引开始选
        return ret;
    }

private:
    void dfs(vector<int>& candidates, int start, int currSum)
    {
        if (currSum == target)
        {
            ret.push_back(path);
            return;
        }

        for (int i = start; i < sz; ++i)
        {
            // 跳过同一层的重复元素
            if (i > start && candidates[i] == candidates[i - 1])
                continue;
            if (currSum + candidates[i] > target) // 剪枝：超了
                break;  // 可 break，因为已排序

            path.push_back(candidates[i]);
            chick[i] = true;
            dfs(candidates, i + 1, currSum + candidates[i]);  // 下一层从 i+1 开始
            path.pop_back();
            chick[i] = false;
        }
    }
};